#include "heaptimer.h"

const int HEAP_INIT_CAPACITY = 64;

HeapTimer::HeapTimer()
{
    heap_.reserve(HEAP_INIT_CAPACITY);
}

HeapTimer::~HeapTimer()
{
    clear();
}

// 向上调整节点，保证小根堆性质
void HeapTimer::siftup(size_t i)
{
    assert(i >= 0 && i < heap_.size());
    size_t j = (i - 1) / 2; // 计算父节点
    while(j >= 0) {
        if(heap_[j] < heap_[i]) {
            break;
        }
        // 交换父子节点
        swapNode(i, j);
        i = j;
        j = (i - 1) / 2;
    }
}

// 交换两个节点
void HeapTimer::swapNode(size_t i, size_t j)
{
    assert(i >= 0 && i < heap_.size());
    assert(j >= 0 && j < heap_.size());
    std::swap(heap_[i], heap_[j]);
    ref_[heap_[i].id_] = i;
    ref_[heap_[j].id_] = j;
}

// 向下调整节点，保证小根堆性质
bool HeapTimer::siftdown(size_t index, size_t n)
{
    assert(index >= 0 && index < heap_.size());
    assert(n >= 0 && n <= heap_.size());
    // 记录当前节点和当前节点的左叶子节点
    size_t i = index;
    size_t j = i * 2 + 1;
    // 下沉操作循环
    while(j < n) {
        // 判断左叶子节点是否小于右叶子节点
        if(j + 1 < n && heap_[j + 1] < heap_[j])
            j++;
        // 当前节点小于右叶子节点
        if(heap_[i] < heap_[j])
            break;
        
        swapNode(i, j);
        i = j;
        j = i * 2 + 1;
    }
    return i > index;
}

// 添加新的任务
void HeapTimer::addNode(int id, int timeOut, const TimeOutCallBack& cb)
{
    assert(id >= 0);
    size_t i;
    // 堆内不存在该任务,在堆尾插入，调整堆
    if(ref_.count(id) == 0) {
        i = heap_.size();
        ref_[id] = i;
        heap_.push_back({id, Clock::now() + MS(timeOut), cb});
        siftup(i);
    } else {
        // 更新超时时间
        i = ref_[id];
        heap_[i].expires_ = Clock::now() + MS(timeOut);
        heap_[i].cb_ = cb;
        if(!siftdown(i, heap_.size())) {
            siftup(i);
        }
    }
}

// 触发超时任务，删除时间节点，执行回调函数
void HeapTimer::doWork(int id)
{
    // 时间节点不存在
    if(heap_.empty() || ref_.count(id) == 0) {
        return;
    }

    size_t i = ref_[id];
    TimerNode node = heap_[i];
    node.cb_();
    deleteNode(i);
}

// 删除指定时间节点
void HeapTimer::deleteNode(size_t index) 
{
    assert(!heap_.empty() && index >= 0 && index < heap_.size());
    // 将要删除的节点调整到队尾，然后调整堆结构
    size_t i = index;
    size_t n = heap_.size() - 1;
    assert(i <= n);
    if(i < n) {
        swapNode(i, n);
        if(!siftdown(i, n)) {
            siftup(i);
        }
    }
    ref_.erase(heap_.back().id_);
    heap_.pop_back();
}

// 调整指定的节点位置 
void HeapTimer::adjust(int id, int timeOut)
{
    assert(!heap_.empty() && ref_.count(id) > 0);
    heap_[ref_[id]].expires_ = Clock::now() + MS(timeOut);
    siftdown(ref_[id], heap_.size());
}

// 检查并执行所有已过期的定时任务
void HeapTimer::tick()
{
    if(heap_.empty()) {
        return;
    }

    // 清除超时节点
    while(!heap_.empty()) {
        TimerNode node = heap_.front();
        // 将任务过期节点减去当前时间并转换为毫秒判断任务是否过期
        if(std::chrono::duration_cast<MS>(node.expires_ - 
            Clock::now()).count() > 0)
        {
            break;
        }
        node.cb_();
        pop();
    }
}

// 删除时间节点
void HeapTimer::pop()
{
    assert(!heap_.empty());
    deleteNode(0);
}

// 清空时间堆
void HeapTimer::clear()
{
    ref_.clear();
    heap_.clear();
}

// 计算下一个最近任务的剩余到期时间
int HeapTimer::getNextTick()
{
    tick();
    int res = -1;
    if(!heap_.empty()) {
        res = std::chrono::duration_cast<MS>(heap_.front().expires_ - 
                Clock::now()).count();
        if(res < 0)
            res = 0;
    }
    return res;
}